package ad_exercise_4.model;

import java.util.HashMap;

/**
 * Representation of a prefix tree used in the LZW compression algorithm.
 * 
 * @author Karen Berntsen (s0815799)
 * @author Erik Stens (s0615374)
 */
public class LZWTree {
	/**
	 * Inner class describing a node in the tree
	 */
	private static class LZWNode {
		private int	character;
		private int	code;
		
		private enum Successor {
			SMALLER, EQUALS, GREATER;
		}
		
		private static final HashMap<Successor, LZWNode>	initialSuccessors	= buildSuccessors();
		
		private final HashMap<Successor, LZWNode>			successors			= new HashMap<Successor, LZWNode>(initialSuccessors);
		
		private static HashMap<Successor, LZWNode> buildSuccessors() {
			HashMap<Successor, LZWNode> successors = new HashMap<Successor, LZWNode>(3);
			for (Successor successor : Successor.values()) {
				successors.put(successor, null);
			}
			return successors;
		}
		
		private LZWNode(int code, int character) {
			this.code = code;
			this.character = character;
		}
	}
	
	private final LZWNode[]	initialNodes	= new LZWNode[256];
	private LZWNode			currentNode;
	private int				currentCode		= -1;
	
	private static final int	NUM_INITIAL_CODES	= 256, MAX_CODE = 4096;
	private int					nextCode			= NUM_INITIAL_CODES;
	
	public LZWTree() {
		for (int i = 0; i < NUM_INITIAL_CODES; i++) {
			initialNodes[i] = new LZWNode(i, i);
		}
	}
	
	public int getCurrentCode() {
		return currentCode;
	}
	
	/**
	 * Method for searching the tree for the next character, adding it if it doesn't exist yet. Searching is always done from the current position within the tree, emulating the addition of a character to an already known prefix, adding the
	 * prefix if the new prefix is unknown
	 * 
	 * @param nextCharacter
	 * @return code of the last known prefix, -1 if the next character added to the current prefix still exists in the tree
	 */
	public int findNextOrAdd(int nextCharacter) {
		if (nextCharacter < 0 || nextCharacter >= NUM_INITIAL_CODES) {
			throw new IllegalArgumentException("Invalid character!");
		}
		
		if (currentNode == null) {
			currentNode = initialNodes[nextCharacter];
			currentCode = currentNode.code;
			return -1;
		}
		
		int result = toNode(nextCharacter, LZWNode.Successor.EQUALS);
		if (result != -1) {
			currentNode = initialNodes[nextCharacter];
			currentCode = currentNode.code;
			return result;
		}
		
		result = findNextRecursive(nextCharacter);
		if (result != -1) {
			currentNode = initialNodes[nextCharacter];
			currentCode = currentNode.code;
		}
		return result;
	}
	
	/**
	 * Method for recursively finding nextCharacter in the tree. If it doesn't exist yet, add it to the tree.
	 * 
	 * @param nextCharacter
	 * @return code of the last known prefix, -1 if the next character added to the current prefix still exists in the tree
	 */
	private int findNextRecursive(int nextCharacter) {
		if (nextCharacter == currentNode.character) {
			currentCode = currentNode.code;
			return -1; // if currentNode represents this character
		}
		
		int result = 0;
		if (nextCharacter < currentNode.character) {
			result = toNode(nextCharacter, LZWNode.Successor.SMALLER); // -1 if the smallerNode existed, otherwise make it and return the current code
		} else if (nextCharacter > currentNode.character) {
			result = toNode(nextCharacter, LZWNode.Successor.GREATER); // -1 if the greaterNode existed, otherwise make it and return the current code
		}
		
		if (result == -1) { // if a smallerNode or greaterNode existed, recursively look from there for the next character
			return findNextRecursive(nextCharacter);
		} else {
			return currentCode;
		}
	}
	
	/**
	 * Continues searching the tree for nextCharacter. If it reaches a null reference, it creates a new node and returns the code of the previously added node
	 * 
	 * @param nextCharacter
	 * @param successor
	 * @return the code of the previously added node
	 */
	private int toNode(int nextCharacter, LZWNode.Successor successor) {
		if (currentNode.successors.get(successor) == null) {
			if (nextCode < MAX_CODE) {
				currentNode.successors.put(successor, new LZWNode(nextCode++, nextCharacter));
			}
			return currentCode;
		}
		currentNode = currentNode.successors.get(successor);
		return -1;
	}
}
